/**
  此方法省内存，但时间有点慢
 * @param {number} n
 * @param {number[][]} paths
 * @return {number[]}
 */

export var gardenNoAdj = function (n, paths) {
  // 只有4种花， 如果花园少于或等于4个，直接在这4种中选便可
  if (n <= 4) return new Array(n).fill(0).map((_, i) => i + 1)
  const ans = new Array(n).fill(0)
  for (let i = 0; i < n; i++) {
    // 找出哪个花园与当前花园相通并记录已用花种号
    const usedFlowers = new Set()
    for (let j = 0; j < paths.length; j++) {
      if (i + 1 === paths[j][0] && ans[paths[j][1] - 1] !== 0) usedFlowers.add(ans[paths[j][1] - 1])
      if (i + 1 === paths[j][1] && ans[paths[j][0] - 1] !== 0) usedFlowers.add(ans[paths[j][0] - 1])
    }
    for (let j = 1; j <= 4; j++) {
      if (!usedFlowers.has(j)) {
        ans[i] = j
        break
      }
    }
  }
  return ans
}

/**
 用多一个数组记录相邻花园，比方法1快很多倍，内存仅用多一点
 * @param {number} n
 * @param {number[][]} paths
 * @return {number[]}
 */

export var gardenNoAdj2 = function (n, paths) {
  // 只有4种花， 如果花园少于或等于4个，直接在这4种中选便可
  if (n <= 4) return new Array(n).fill(0).map((_, i) => i + 1)
  // 记录相邻花园
  const nextNodes = new Array(n).fill(0).map(() => new Set())
  for (let i = 0; i < paths.length; i++) {
    nextNodes[paths[i][0] - 1].add(paths[i][1] - 1)
    nextNodes[paths[i][1] - 1].add(paths[i][0] - 1)
  }
  const ans = new Array(n).fill(0)
  for (let i = 0; i < n; i++) {
    // 找出哪个花园与当前花园相通并记录已用花种号
    const usedFlowers = new Set()
    for (let j of nextNodes[i]) {
      usedFlowers.add(ans[j])
    }
    for (let j = 1; j <= 4; j++) {
      if (!usedFlowers.has(j)) {
        ans[i] = j
        break
      }
    }
  }
  return ans
}
